package cn.zifangsky.stack;

import cn.zifangsky.linkedlist.SinglyNode;

import java.util.EmptyStackException;

/**
 * 基于单链表实现的栈
 * 2017-07-12：使用泛型改成通用形式
 * @author zifangsky
 * @param <K>
 */
public class LinkStack<K> implements Stack<K> {

	private SinglyNode<K> headNode;
	
	@Override
	public boolean isFull() {
		return false;
	}

	@Override
	public boolean contains(K k) {
        if(k != null){
            SinglyNode<K> temp = headNode;
            while (temp != null){
                if(temp.getData().equals(k)){
                    return true;
                }
                temp = temp.getNext();
            }
        }

        return false;
	}

	/**
	 * 返回栈是否是空栈
	 * @时间复杂度 O(1)
	 * @return
	 */
	@Override
    public boolean isEmpty(){
		return headNode == null ? true : false;
	}
	
	/**
	 * 入栈
	 * @时间复杂度 O(1)
	 * @param data 入栈数据
	 */
	@Override
	public void push(K data){
		if(headNode == null){
			headNode = new SinglyNode<K>(data);
		}else{
			SinglyNode<K> newNode = new SinglyNode<K>(data);
			newNode.setNext(headNode);
			headNode = newNode;
		}
	}
	
	/**
	 * 出栈：移动栈顶指针并返回数据
	 * @时间复杂度 O(1)
	 * @return
	 */
	@Override
	public K pop(){
		if(headNode == null){
			throw new EmptyStackException();
		}else{
			K data = headNode.getData();
			headNode = headNode.getNext();
			return data;
		}
	}
	
	/**
	 * 返回最后一个插入栈的元素，但不删除
	 * @时间复杂度 O(1)
	 * @return
	 */
	@Override
	public K top(){
		if(headNode == null){
			throw new EmptyStackException();
		}else{
			return headNode.getData();
		}
	}
	
	/**
	 * 返回存储在栈中的元素个数
	 * @时间复杂度 O(n)
	 * @return
	 */
	@Override
	public int size(){
		if(headNode == null){
			return 0;
		}else{
			int length = 0;
			SinglyNode<K> currentNode = headNode;
			while (currentNode != null) {
				length++;
				currentNode = currentNode.getNext();
			}
			return length;
		}
	}
	
	/**
	 * 删除整个栈
	 * @时间复杂度 O(1)
	 */
	@Override
	public void deleteStack(){
		headNode = null;
	}

	/**
	 * 遍历整个栈
	 * @时间复杂度 O(n)
	 * @return
	 */
	@Override
	public void print() {
		SinglyNode<K> tmpNode = headNode;
		printFromEnd(tmpNode);
	}
	
	/**
	 * 思路：递归，从链表末尾开始输出
	 * @时间复杂度 O(n)
	 * @param headNode
	 * @return
	 */
	public void printFromEnd(SinglyNode<K> headNode){
		if(headNode != null){
			if(headNode.getNext() != null){
				printFromEnd(headNode.getNext());
			}
			
			System.out.print(headNode.getData() + " ");
		}
	}

}
